Branch prediction enables a processor to begin executing instructions before a branch outcome is certain. That is, previous history and/or patterns are used to predict an outcome of a branch. Typically when a procedure branches to another procedure, a call instruction (e.g., either a jump-and-link or jump-and-link-register instructions) may push a return address into a return-address stack. The return-address stack is a data area or buffer used to store return addresses that need to be handled. In particular, the return-address stack is a push-down list such that old return addresses are pushed down as new return addresses come in. When a return instruction in a procedure is executed, a return address may pop up from the return-address stack. In a last-in, first-out (LIFO) approach, a processor may take its next return address from the top of the return-address stack. Based on the popped-up return address, the processor may predict the target of the next instruction to execute.
The size of the return-address stack, however, may be limited because of cost associated with implementing the return-address stack on an integrated circuit. This is problematic for applications with a large number of call chains (i.e., procedures that call other procedures). When the return-address stack is full, a stack push operation initiated by an additional call instruction may cause the return-address stack to overflow. Especially for procedures that simply call other procedures, the processor loses its prior knowledge of the return address associated with the executed call instruction (i.e., overwriting the oldest entry of return addresses in the stack). As a result, the target of a number of return instructions may be mispredicted.